package leetcode.code0472;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

/**
 * 43 / 44 个通过测试用例 状态：超出时间限制 提交时间：1 分钟前
 */
public class Solution2 implements IDebug {

	Node root;

	public List<String> findAllConcatenatedWordsInADict(String[] words) {
		Arrays.sort(words, (a, b) -> a.length() - b.length());
		List<String> ans = new ArrayList<>();
		root = new Node();
		// [cat, dog, rat, cats, dogcatsdog, catsdogcats, ratcatdogcat, hippopotamuses]
		for (String word : words) {
			if (root.add(word)) {
				ans.add(word);
			}
		}
		return ans;
	}

	class Node {
		Node[] character;
		int words;

		public Node() {
			character = new Node[26];
		}

		public boolean add(String word) {
			char[] w = word.toCharArray();
			Node node = root;
			List<Info> starters = new ArrayList<>();
			int len = word.length();
			for (int i = 0; i < len; i++) {
				char c = w[i];
				int index = c - 'a';
				if (node.character[index] == null) {
					node.character[index] = new Node();
				}
				node = node.character[index];
				if (node.words > 0 && i + 1 < len) {
					Info info = new Info();
					info.starter = node;
					info.words = node.words;
					info.rest = new String(w, i + 1, len - i - 1);
					starters.add(info);
				}
			}
			for (int i = starters.size() - 1; i >= 0; i--) {
				Info info = starters.get(i);
				int words = div(info.starter, info.rest, info.words + 1);
				if (words > 1) {
					node.words = words;
					return true;
				}
			}
			node.words = 1;
			return false;
		}

		public int div(Node starter, String rest, int words) {
			Node search = root;
			Node node = starter;
			char[] w = rest.toCharArray();
			int len = w.length;
			List<Info> starters = new ArrayList<>();
			for (int i = 0; i < w.length; i++) {
				char c = w[i];
				int index = c - 'a';
				if (search.character[index] == null) {
					search = search.character[index];
					break;
				}
				search = search.character[index];
				node = node.character[index];
				if (search.words > 0 && i + 1 < len) {
					node.words = words;
					Info info = new Info();
					info.starter = node;
					info.words = words;
					info.rest = new String(w, i + 1, len - i - 1);
					starters.add(info);
				}
			}
			if (search != null && search.words == 1) {
				return words;
			}
			for (int i = starters.size() - 1; i >= 0; i--) {
				Info info = starters.get(i);
				int tmp = div(info.starter, info.rest, info.words + 1);
				if (tmp > 1) {
					node.words = tmp;
					return tmp;
				}
			}
			return 0;
		}

	}

	class Info {
		Node starter;
		String rest;
		int words;
	}

	@Override
	public void debug1() {
		List<String> e = HelpDebug.str2liststr("[\"catsdogcats\",\"dogcatsdog\",\"ratcatdogcat\"]");
		HelpDebug.compare(e, this.findAllConcatenatedWordsInADict(HelpDebug.str2array2(
				"[\"cat\",\"cats\",\"catsdogcats\",\"dog\",\"dogcatsdog\",\"hippopotamuses\",\"rat\",\"ratcatdogcat\",\"dogcatsdogs\",\"catsdogs\"]")));

	}

	@Override
	public void debug2() {
		List<String> e = HelpDebug.str2liststr("[\"catsdogcats\",\"dogcatsdog\",\"ratcatdogcat\"]");
		HelpDebug.compare(e, this.findAllConcatenatedWordsInADict(HelpDebug.str2array2(
				"[\"cat\",\"cats\",\"catsdogcats\",\"dog\",\"dogcatsdog\",\"hippopotamuses\",\"rat\",\"ratcatdogcat\"]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug1();

	}

}
